<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(A卷,200分)- 快递投放问题（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>有N个快递站点用字符串标识&#xff0c;某些站点之间有道路连接。<br /> 每个站点有一些包裹要运输&#xff0c;每个站点间的包裹不重复&#xff0c;路上有检查站会导致部分货物无法通行&#xff0c;计算哪些货物无法正常投递&#xff1f;</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<ul><li>第一行输入M N&#xff0c;M个包裹N个道路信息.</li><li>0&lt;&#61;M,N&lt;&#61;100&#xff0c;</li><li>检查站禁止通行的包裹如果有多个以空格分开</li></ul> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<ul><li>输出不能送达的包裹&#xff0c;如&#xff1a;package2 package4&#xff0c;</li><li>如果所有包裹都可以送达则输出&#xff1a;none&#xff0c;</li><li>输出结果按照升序排列。</li></ul> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">4 2<br /> package1 A C<br /> package2 A C<br /> package3 B C<br /> package4 A C<br /> A B package1<br /> A C package2</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">package2</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">无</td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>这题。。。。我能说我读都费劲嘛。。。</p> 
<p>这题意思我只能猜一猜&#xff0c;因为我无法肯定自己的理解是对的。</p> 
<p></p> 
<p>用例第一行</p> 
<ul><li>输入的4代表有4个包裹&#xff0c;分别是package1、package2、package3、package4</li><li>输入的2代表&#xff1a;有2个&#xff1a;两站点之间无法通行的包裹&#xff0c;比如A B package1 代表A、B站点之间无法通行包裹package1。</li></ul> 
<p>用例第2~5行&#xff08;对应第一行输入的4&#xff09;&#xff0c;对应4个包裹&#xff0c;以及它们要从哪个站点发往哪个站点。比如package1 A C&#xff0c;表示package1要从A发往C站点。</p> 
<p>用例第6~7行&#xff08;对应第二行输入的2&#xff09;&#xff0c;表示两站点之间无法通行的包裹。</p> 
<p></p> 
<p>因此&#xff0c;按照上面理解&#xff1a;</p> 
<p>A-B无法通行package1&#xff0c;但是package1要从A发往C&#xff0c;因此不受影响。</p> 
<p>A-C无法通行package2&#xff0c;而package2刚好要从A发往C&#xff0c;因此受到影响&#xff0c;无法发送。</p> 
<p>因此最后&#xff0c;只有package2无法发送。</p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JavaScript算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
let m, n;
let want, cant;
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61;&#61; 1) {
    [m, n] &#61; lines[0].split(&#34; &#34;).map(Number);
  }

  if (m !&#61;&#61; undefined &amp;&amp; lines.length &#61;&#61;&#61; m &#43; 1) {
    want &#61; lines.slice(1).map((line) &#61;&gt; line.split(&#34; &#34;));
  }

  if (n !&#61;&#61; undefined &amp;&amp; lines.length &#61;&#61;&#61; m &#43; n &#43; 1) {
    cant &#61; lines.slice(m &#43; 1).map((line) &#61;&gt; line.split(&#34; &#34;));

    console.log(getResult(want, cant));
    lines.length &#61; 0;
  }
});

/**
 * &#64;param {*} want 二维数组&#xff0c;元素是 [包裹&#xff0c; 起始站点&#xff0c; 目的站点]
 * &#64;param {*} cant 二维数组&#xff0c;元素是 [起始站点&#xff0c; 目的站点&#xff0c;...无法通行的货物列表]
 */
function getResult(want, cant) {
  const wantObj &#61; {};
  const cantObj &#61; {};

  for (let arr of want) {
    const [package, src, dst] &#61; arr;
    const path &#61; &#96;${src}-${dst}&#96;;
    wantObj[path] ? wantObj[path].push(package) : (wantObj[path] &#61; [package]);
  }

  for (let arr of cant) {
    const src &#61; arr[0];
    const dst &#61; arr[1];
    const path &#61; &#96;${src}-${dst}&#96;;

    const packages &#61; arr.slice(2);
    cantObj[path] ? cantObj[path].push(...packages) : (cantObj[path] &#61; [...packages]);
  }

  let ans &#61; [];
  for (let path in wantObj) {
    const wantPKG &#61; new Set(wantObj[path]);
    const cantPKG &#61; new Set(cantObj[path]);

    wantPKG.forEach((pkg) &#61;&gt; {
      if (cantPKG.has(pkg)) {
        ans.push(pkg);
      }
    });
  }

  if (!ans.length) return &#34;none&#34;;

  return ans.sort((a, b) &#61;&gt; Number(a.slice(7)) - Number(b.slice(7))).join(&#34; &#34;);
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    Integer[] tmp &#61;
        Arrays.stream(sc.nextLine().split(&#34; &#34;)).map(Integer::parseInt).toArray(Integer[]::new);
    int m &#61; tmp[0];
    int n &#61; tmp[1];

    String[][] want &#61; new String[m][];
    for (int i &#61; 0; i &lt; m; i&#43;&#43;) {
      want[i] &#61; sc.nextLine().split(&#34; &#34;);
    }

    String[][] cant &#61; new String[n][];
    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
      cant[i] &#61; sc.nextLine().split(&#34; &#34;);
    }

    System.out.println(getResult(want, cant));
  }

  /**
   * &#64;param want 二维数组&#xff0c;元素是 [包裹&#xff0c; 起始站点&#xff0c; 目的站点]
   * &#64;param cant 二维数组&#xff0c;元素是 [起始站点&#xff0c; 目的站点&#xff0c;...无法通行的包裹列表]
   * &#64;return 无法通行的包裹
   */
  public static String getResult(String[][] want, String[][] cant) {
    HashMap&lt;String, HashSet&lt;String&gt;&gt; wantMap &#61; new HashMap&lt;&gt;();
    HashMap&lt;String, HashSet&lt;String&gt;&gt; cantMap &#61; new HashMap&lt;&gt;();

    for (String[] arr : want) {
      String pkg &#61; arr[0];
      String path &#61; arr[1] &#43; &#34;-&#34; &#43; arr[2];
      wantMap.putIfAbsent(path, new HashSet&lt;&gt;());
      wantMap.get(path).add(pkg);
    }

    for (String[] arr : cant) {
      String path &#61; arr[0] &#43; &#34;-&#34; &#43; arr[1];
      String[] pkgs &#61; Arrays.copyOfRange(arr, 2, arr.length);
      cantMap.putIfAbsent(path, new HashSet&lt;&gt;());
      cantMap.get(path).addAll(Arrays.asList(pkgs));
    }

    ArrayList&lt;String&gt; ans &#61; new ArrayList&lt;&gt;();

    for (String path : wantMap.keySet()) {
      HashSet&lt;String&gt; wantPKG &#61; wantMap.get(path);
      HashSet&lt;String&gt; cantPKG &#61; cantMap.get(path);

      if (cantPKG &#61;&#61; null) continue;

      for (String pkg : wantPKG) {
        if (cantPKG.contains(pkg)) {
          ans.add(pkg);
        }
      }
    }

    if (ans.size() &#61;&#61; 0) return &#34;none&#34;;

    ans.sort((a, b) -&gt; Integer.parseInt(a.substring(7)) - Integer.parseInt(b.substring(7)));

    StringJoiner sj &#61; new StringJoiner(&#34; &#34;);
    for (String an : ans) {
      sj.add(an);
    }
    return sj.toString();
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
m, n &#61; map(int, input().split())

want &#61; []
for i in range(m):
    want.append(input().split())

cant &#61; []
for i in range(n):
    cant.append(input().split())


# 算法入口
def getResult(want, cant):
    &#34;&#34;&#34;
    :param want: 二维数组&#xff0c;元素是 [包裹&#xff0c; 起始站点&#xff0c; 目的站点]
    :param cant: 二维数组&#xff0c;元素是 [起始站点&#xff0c; 目的站点&#xff0c;...无法通行的货物列表]
    :return: 不能送达的包裹
    &#34;&#34;&#34;
    wantDict &#61; {}
    cantDict &#61; {}

    for arr in want:
        package, src, dst &#61; arr
        path &#61; f&#34;{src}-{dst}&#34;
        if wantDict.get(path) is None:
            wantDict[path] &#61; [package]
        else:
            wantDict[path].append(package)

    for arr in cant:
        src &#61; arr[0]
        dst &#61; arr[1]
        path &#61; f&#34;{src}-{dst}&#34;
        packages &#61; arr[2:]
        if cantDict.get(path) is None:
            cantDict[path] &#61; packages[::]
        else:
            cantDict[path].extend(packages)

    ans &#61; []
    for path in wantDict.keys():
        if cantDict.get(path) is None:
            continue

        wantPKG &#61; set(wantDict[path])
        cantPKG &#61; set(cantDict[path])

        for pkg in wantPKG:
            if pkg in cantPKG:
                ans.append(pkg)

    if len(ans) &gt; 0:
        ans.sort(key&#61;lambda x: int(x[7:]))
        return &#34; &#34;.join(ans)
    else:
        return &#34;none&#34;


print(getResult(want, cant))
</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>